Arrays in Compiler

• Column Major Mapping

Column Major Mapping

---

This is for indexes that starts at 0

int A[3][4]

Previously with row major mapping we filled the rows linearly.

Now we fill the columns linearly.

$$ \newcommand\T{\Rule{0pt}{1em}{.3em}} \begin{array}{|r|r|r|r|r|r|r|r|r|r|r|r|r|} \hline \text{index}\T& 1\T&2\T&3\T&4\T&5\T&6\T&7\T&8\T&9\T&10\T&11\T&12 \\\hline \text{array}\T&A_{00}\T&A_{10}\T&A_{20}\T&A_{01}\T&A_{11}\T&A_{21}\T&A_{02}\T&A_{12}\T&A_{22}\T&A_{03}\T&A_{13}\T&A_{23} \\\hline \text{address}\T&_{200/201}\T&_{2/3}\T&_{4/5}\T&_{6/7}\T&_{8/9}\T&_{10/11}\T&_{12/13}\T&_{14/15}\T&_{16/17}\T&_{18/19}\T&_{20/21}\T&_{222/223} \\\hline \end{array} $$$$ \newcommand\T{\Rule{0pt}{1em}{.3em}} \begin{array}{|r|r|r|r|} \hline A_{00} \T & A_{01} \T & A_{02} \T & A_{03} \\\hline A_{10} \T & A_{11} \T & A_{12} \T & A_{13} \\\hline A_{20} \T & A_{21} \T & A_{22} \T & A_{23} \\\hline \end{array} $$

E.g.

$$\text{Address of A[0][0]} = A_{00}$$$$\text{Address of A[1][0]} = A_{10}$$$$\text{Address of A[2][0]} = A_{20}$$

This will be identified as $col_{0}$

$$\text{Address of A[0][1]} = A_{01}$$$$\text{Address of A[1][1]} = A_{11}$$$$\text{Address of A[2][1]} = A_{21}$$

This will be identified as $col_{1}$

$$\text{Address of A[0][2]} = A_{02}$$$$\text{Address of A[1][2]} = A_{12}$$$$\text{Address of A[2][2]} = A_{22}$$

This will be identified as $col_{2}$

$$\text{Address of A[0][3]} = A_{03}$$$$\text{Address of A[1][3]} = A_{13}$$$$\text{Address of A[2][3]} = A_{23}$$

This will be identified as $col_{3}$

To get the address for A[1][2]: $$ $$ $$\text{Address of A[1][2]} = 200 + [2\times3 + 1]\times 2$$ $$ $$

$$\text{Address of A[1][2]} = 214$$

To get the address for A[2][3]: $$ $$

$$\text{Address of A[2][3]} = 200 + [2\times4 + 3]\times 2$$$$ $$$$\text{Address of A[2][3]} = 222$$

To get the address for A[1][3]: $$ $$

$$\text{Address of A[1][3]} = 200 + [3\times3 + 1]\times 2$$$$ $$$$\text{Address of A[1][3]} = 220$$$$ $$$$ $$

Address of any location - COLUMN MAJOR FORMULA USED BY COMPILER:

$$\text{Address of A[i][j]} = L_0 + [j\times m + i]\times w$$$$ $$$$(\text{int } A[m][n])$$$$(\text{int } A[i][j])$$$$ $$$$\text{where } i = \text{the row index}$$$$\text{where } j = \text{the column index}$$$$\text{where } m = \text{total rows of array}$$$$\text{where } n = \text{total colums of array}$$$$ \newcommand\T{\Rule{0pt}{1em}{.3em}} \begin{array}{|r|r|} \hline i\T & \text{row index} \\\hline j\T & \text{column index} \\\hline m\T & \text{total rows of array} \\\hline n\T & \text{total columns of array} \\\hline w\T & \text{size of data type in bytes} \\\hline \end{array} $$$$ $$$$ $$

Comparison Row Major and Column Mapping

---

$$ $$$$(\text{int } A[m][n])$$$$(\text{int } A[i][j])$$$$ $$$$ $$

\text{where } i = \text{the row index}$$ $$\text{where } j = \text{the column index}$$ $$\text{where } m = \text{total rows of array}$$ $$\text{where } n = \text{total colums of array}$$

$$ \newcommand\T{\Rule{0pt}{1em}{.3em}} \begin{array}{|r|r|} \hline i\T & \text{row index} \\\hline j\T & \text{column index} \\\hline m\T & \text{total rows of array} \\\hline n\T & \text{total columns of array} \\\hline w\T & \text{size of data type in bytes} \\\hline \end{array} $$$$ $$$$\text{ROW MAJOR MAPPING FORMULA USED BY COMPILER}$$$$\text{Address of A[i][j]} = L_0 + [i\times n + j]\times w$$$$ $$$$\text{COLUMN MAJOR MAPPING FORMULA USED BY COMPILER}$$$$\text{Address of A[i][j]} = L_0 + [j\times m + i]\times w$$

With row major mapping we go from right to left (j, i). With row major mapping we go from left to right (i, j);

Both use the same number of operation, so both are efficient. But C++ compiler uses row major mapping.